For any $\ell > 0$, we present an algorithm which takes as input asemi-algebraic set, $S$, defined by $P_1 \leq 0,...,P_s \leq 0$, where each$P_i \in \R[X_1,...,X_k]$ has degree $\leq 2,$ and computes the top $\ell$Betti numbers of $S$, $b_{k-1}(S), ..., b_{k-\ell}(S),$ in polynomial time. Thecomplexity of the algorithm, stated more precisely, is $ \sum_{i=0}^{\ell+2} {s\choose i} k^{2^{O(\min(\ell,s))}}. $ For fixed $\ell$, the complexity of thealgorithm can be expressed as $s^{\ell+2} k^{2^{O(\ell)}},$ which is polynomialin the input parameters $s$ and $k$. To our knowledge this is the firstpolynomial time algorithm for computing non-trivial topological invariants ofsemi-algebraic sets in $\R^k$ defined by polynomial inequalities, where thenumber of inequalities is not fixed and the polynomials are allowed to havedegree greater than one. For fixed $s$, we obtain by letting $\ell = k$, analgorithm for computing all the Betti numbers of $S$ whose complexity is$k^{2^{O(s)}}$.
展开▼
机译：对于任何$ \ ell> 0 $，我们提出一种算法，该算法以输入半对称代数集$ S $作为输入，由$ P_1 \ leq 0，...，P_s \ leq 0 $定义，其中每个$ P_i \ in \ R [X_1，...，X_k] $具有度数\ leq 2，$，并计算$ S $，$ b_ {k-1}（S），...， b_ {k- \ ell}（S），$多项式时间。更精确地说，算法的复杂度是$ \ sum_ {i = 0} ^ {\ ell + 2} {s \选择i} k ^ {2 ^ {O（\ min（\ ell，s））}}} 。对于固定的$ \ ell $，算法的复杂度可以表示为$ s ^ {\ ell + 2} k ^ {2 ^ {O（\ ell）}}，$在输入参数$ s $和$ k $。据我们所知，这是用于计算由多项式不等式定义的$ \ R ^ k $中的半代数集的非平凡拓扑不变量的第一个多项式时间算法，其中不等式的数量不是固定的，并且多项式的阶数可以大于1。对于固定的$ s $，我们通过让$ \ ell = k $来获得计算复杂度为$ k ^ {2 ^ {O（s）}} $的$ S $的所有贝蒂数的算法。
展开▼
